package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-19
 */

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class leetcode5 {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n<=1) return s;
        int maxLen = 0;
        String max = "";

        boolean[][] dp = new boolean[n][n];
        for (int right = 1; right < n; right++) {
            for (int left = 0; left < right; left++) {
                if (s.charAt(left)!=s.charAt(right)) continue;

                if (right-left<=2) dp[left][right] = true;
                else dp[left][right] = dp[left+1][right-1];

                if (dp[left][right] && right-left+1>maxLen){
                    max = s.substring(left,right+1);
                    maxLen = right-left+1;
                }
            }
        }

        if (max.equals("")) return String.valueOf(s.charAt(0));
        return max;
    }
}
